package com.atguigu.sort;


public class InsertSort {

    private InsertSort() {
    }

    public static <E extends Comparable<E>> void Sort(E[] arr) {

        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j - 1]) < 0; j--) {
                swap(arr, j, j - 1);
            }

        }
    }

    public static <E extends Comparable<E>> void Sort2(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            E value = arr[i];
            int j;
            for (j = i; j > 0 && arr[j - 1].compareTo(value) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = value;
        }
    }

    private static <E extends Comparable<E>> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static <E extends Comparable<E>> void Sort(E[] arr, int l, int r) {
        if (l < 0 || r >= arr.length) {
            throw new IllegalArgumentException("sort failed , index illegal!");
        }
        for (int i = l; i <= r; i++) {
            E value = arr[i];
            int j;
            for (j = i; j > l && arr[j - 1].compareTo(value) > 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = value;
        }
    }


}
